#include <iostream>
#define MAXN 30
#define MAXM 2005
using namespace std;
int cost[MAXN];
char s[MAXM];
int N, M;
int dp[MAXM][MAXM];
void solve();
int main() {
    cin >> N >> M;
    cin >> s;
    char x; int a, d;
    for (int i = 0; i < N; i++) {
        cin >> x >> a >> d;
        cost[x - 'a'] = min(a, d);
    }
    solve();
}

void solve() {
    for (int j = 1; j < M; j++) {
        for (int i = j - 1; i >= 0; i--) {
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
            else dp[i][j] = min(dp[i + 1][j] + cost[s[i] - 'a'], dp[i][j - 1] + cost[s[j] - 'a']);
        }
    }
    cout << dp[0][M - 1] << endl;
}